#include <malloc.h>

typedef char DataType;
typedef struct node
{
    DataType data;
    struct node *lchild, *rchild;
} BinTNode;
typedef BinTNode *BinTree;

int count(BinTree T)
{
    if (!T)
        return 0;
    return count(T->lchild) + count(T->rchild) + 1;
}

int leaf(BinTree T)
{
    int nl, nr;
    if (!T)
        return 0;
    if (T && T->lchild == NULL && T->rchild == NULL)
        return 1;
    if (T->lchild)
        nl = leaf(T->lchild);
    if (T->rchild)
        nr = leaf(T->rchild);
    return nl + nr;
}

#define M 10
int Width(BinTree T)
{
    int static n[M];
    int static i = 1;
    int static max = 0;
    if (!T)
        return 0;
    if (i == 1)
    {
        n[i]++;
        i++;
        if (T->lchild)
            n[i]++;
        if (T->rchild)
            n[i]++;
    }
    else
    {
        i++;
        if (T->lchild)
            n[i]++;
        if (T->rchild)
            n[i]++;
    }
    if (max < n[i])
        max = n[i];
    Width(T->lchild);
    i--;
    Width(T->rchild);
    return max;
}

void swap(BinTree T)
{
    BinTree tmp;
    if (!T)
        return;
    swap(T->lchild);
    swap(T->rchild);
    tmp = T->lchild;
    T->lchild = T->rchild;
    T->rchild = tmp;
}

BinTree CopyTree(BinTree root)
{
    BinTree new_node;
    if (!root)
        return NULL;
    new_node = (BinTNode *)malloc(sizeof(BinTNode));
    new_node->data = root->data;
    new_node->lchild = CopyTree(root->lchild);
    new_node->rchild = CopyTree(root->rchild);
    return new_node;
}

BinTree SearchBinTree(BinTree T, DataType x)
{
    BinTree result;
    if (!T)
        return NULL;
    if (T->data == x)
        return T;
    result = SearchBinTree(T->lchild, x);
    if (result)
        return result;
    return SearchBinTree(T->rchild, x);
}

//求节点x所在层数
int InLevel(BinTree T, DataType x)
{
    int static l = 0;
    if (!T)
        return 0;
    if (l == 0)
    {
        l++;
        if (T->data == x)
            return l;
        if (T->lchild || T->rchild)
            l++;
    }
    else
    {
        if (T->data == x)
            return l;
        if (T->lchild || T->rchild)
            l++;
        else
            return 0;
    }
    InLevel(T->lchild, x);
    InLevel(T->rchild, x);
}